package ShuJuJieGou;
import java.util.Scanner;

public class SequentialList {
    private int[] list;
    private int size;

    // 构造函数，初始化顺序表
    public SequentialList(int capacity) {
        list = new int[capacity];
        size = 0;
    }

    // 创建顺序表
    public void create(int[] elements) {
        for (int element : elements) {
            list[size++] = element;
        }
        sort();
        System.out.println("创建成功！");
    }

    // 插入元素
    public void insert(int position, int element) {
        if (position < 1 || position > size + 1) {
            System.out.println("插入位置非法！");
            return;
        }
        if (size == list.length) {
            resize();
        }
        for (int i = size; i >= position; i--) {
            list[i] = list[i - 1];
        }
        list[position - 1] = element;
        size++;
        System.out.println("插入成功！！！");
    }

    // 删除元素
    public void delete(int position) {
        if (position < 1 || position > size) {
            System.out.println("删除位置非法！");
            return;
        }
        for (int i = position - 1; i < size - 1; i++) {
            list[i] = list[i + 1];
        }
        size--;
        System.out.println("删除成功！！！");
    }

    // 顺序查找
    public int sequentialSearch(int value) {
        for (int i = 0; i < size; i++) {
            if (list[i] == value) {
                return i + 1;
            }
        }
        return -1;
    }

    // 折半查找
    public int binarySearch(int value) {
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list[mid] == value) {
                return mid + 1;
            } else if (list[mid] < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    // 倒置顺序表
    public void reverse() {
        for (int i = 0; i < size / 2; i++) {
            int temp = list[i];
            list[i] = list[size - 1 - i];
            list[size - 1 - i] = temp;
        }
        System.out.println("倒置成功！");
    }

    // 输出顺序表
    public void printList() {
        System.out.print("当前顺序表所有元素:");
        for (int i = 0; i < size; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println();
    }

    // 清空顺序表
    public void clear() {
        size = 0;
        System.out.println("顺序表已清空！");
    }

    // 排序（简单的冒泡排序）
    public void sort() {
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
        System.out.println("排序成功！！！");
    }

    // 扩容
    private void resize() {
        int[] newList = new int[list.length * 2];
        System.arraycopy(list, 0, newList, 0, size);
        list = newList;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        SequentialList sequentialList = null;

        while (true) {
            System.out.println("please select the operation you want:");
            System.out.println("1. 创建");
            System.out.println("2. 插入");
            System.out.println("3. 删除");
            System.out.println("4. 顺序查找");
            System.out.println("5. 折半查找");
            System.out.println("6. 倒置");
            System.out.println("7. 输出");
            System.out.println("8. 清空");
            System.out.println("9. 排序");
            System.out.println("0. 退出");
            System.out.print(">>>>请选择你的操作：");
            int choice = scanner.nextInt();

            switch (choice) {
                case 1:
                    System.out.print("请输入要创建的顺序表长度(>1):");
                    int length = scanner.nextInt();
                    int[] elements = new int[length];
                    System.out.print("请输入" + length + "个数（空格隔开,可无序输入）:");
                    for (int i = 0; i < length; i++) {
                        elements[i] = scanner.nextInt();
                    }
                    sequentialList = new SequentialList(length);
                    sequentialList.create(elements);
                    sequentialList.printList();
                    break;
                case 2:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要插入的位置(从1开始)及元素:");
                    int position = scanner.nextInt();
                    int element = scanner.nextInt();
                    sequentialList.insert(position, element);
                    sequentialList.printList();
                    break;
                case 3:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要删除的位置(从1开始):");
                    position = scanner.nextInt();
                    sequentialList.delete(position);
                    sequentialList.printList();
                    break;
                case 4:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要查找的值:");
                    int searchValue = scanner.nextInt();
                    int result = sequentialList.sequentialSearch(searchValue);
                    if (result != -1) {
                        System.out.println("该元素位置为:" + result);
                    } else {
                        System.out.println("未找到该元素！");
                    }
                    break;
                case 5:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要查找的值:");
                    searchValue = scanner.nextInt();
                    result = sequentialList.binarySearch(searchValue);
                    if (result != -1) {
                        System.out.println("该元素位置为:" + result);
                    } else {
                        System.out.println("未找到该元素！");
                    }
                    break;
                case 6:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    sequentialList.reverse();
                    sequentialList.printList();
                    break;
                case 7:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    sequentialList.printList();
                    break;
                case 8:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    sequentialList.clear();
                    break;
                case 9:
                    if (sequentialList == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    sequentialList.sort();
                    sequentialList.printList();
                    break;
                case 0:
                    System.out.println("程序退出！");
                    scanner.close();
                    System.exit(0);
                default:
                    System.out.println("输入错误！");
            }
        }
    }
}

